n=1000;
q=1000;
index=[4299254,3202005,7478529,5379540,70501,9729447,3539840,9879640,8644520,6267557,6727720,4955250,7743780,1053036,766299,7024954,3733542,8907962,8634219,6523788,2667278,8978264,2982080,1845932,6879460,1399265,3343045,1312892,935027,4865803,4845600,7522390,3406960,903357,2429160,1835378,8090216,4115616,9791710,6326995,5769572,7742351,8971340,2367055,642264,4219575,5661586,4192940,4297328,3240864,6722831,6018597,1325914,1055790,1909430,259164,3047653,364804,3863200,7602200,8706792,6328050,8774432,623932,9573840,3636558,8791302,1918364,7719168,440393,9412762,6401373,7081104,4531648,5104283,5271271,124400,1509140,4530322,8011008,8113696,5153932,9915901,511530,1931216,4844454,2015705,986560,8916040,1250234,6997698,7603485,6478544,7082534,5930693,2862194,7468194,2777988,7037214,5754017,8864552,7925736,9895495,1524640,8559608,3950688,6965354,3059401,8855608,4943620,1135732,287925,7961320,8362890,5814814,6821237,5089769,627475,5154620,8630160,4468286,4068982,3734578,5137549,8743290,9720342,5792028,46336,7178348,1022623,8103872,8398160,844370,6820302,5017504,8676640,2419041,4720129,3984435,1049080,1065012,1602104,6451520,4736205,6824400,2954048,9773080,9189481,9556289,7616900,1231648,7732669,9267398,2924176,7618360,3235840,3365601,9474508,5697690,9676960,4097625,6579594,6252005,1613604,3977985,2574253,2671004,4080544,2169399,3268996,8600890,3014489,9405412,3768164,5611632,5496683,3739200,3155488,6181167,6320364,4590180,6102400,5092210,6219128,2108753,9340995,719372,8985055,2762240,1885008,4964280,6117936,2428124,5770945,3711682,2666336,9482020,9143024,3524340,9965020,1382218,3554176,3686215,5365170,7501432,8476970,5646891,2679940,5056071,4164365,8360768,7874431,2193035,1891520,7455367,8521834,3133558,2050722,8961984,4873502,6550874,3708338,9592505,4356220,5033100,9792319,6928145,8500474,8401910,5960013,2858000,5062850,2827808,7570686,9128574,7123779,6253714,8332796,8139200,4432366,422100,6460212,5843250,8587953,677696,3336768,5134800,1134406,4834010,9664168,8848390,9945878,8123892,9515885,9486954,8377844,8545560,3839440,6427052,1171080,773560,382325,74628,9795735,7283819,1882461,9052770,397764,2758874,2408625,6580536,7762670,4588250,5355852,9056983,1935786,5936632,4858341,2546508,415424,1487048,176030,9000840,9013167,3465340,4502122,3948680,2866400,4036549,1698386,902127,6480535,2678325,6563680,5228200,5778548,7222349,5522030,2887495,7878820,8261290,5470850,4906828,8231326,8528008,7542900,2757543,2548498,6221115,6227685,4236070,6898962,5559757,9649421,9483440,7458872,6796463,7579098,5774470,6890370,5541397,2162112,9801714,4625334,614986,4406220,311330,2074900,536704,8791776,6413530,8108100,4114804,4139320,7218901,9794597,8713732,3955915,9572893,8416010,9753937,7770660,712628,4863840,2325248,1001996,4861051,5624767,3717276,284676,3684466,495332,1762500,7218539,4476894,75148,7435857,1780184,7204180,3227286,698726,7808430,8795200,6566960,7474866,685183,9269178,3794916,5858830,6069120,4891898,8537477,2442114,2493332,9212729,8686026,6660290,9945290,2293824,88935,8250628,5118097,8298302,7181724,8482275,5443022,6671222,5920343,9737946,3827,4778835,5385745,1443420,700110,2086304,3820425,5583620,7808850,5258288,9672848,1814912,3810725,4935984,999250,4907458,2082000,6572920,6626604,4988160,4667923,6165600,5473126,8134368,3238926,6940674,1965947,4370350,6277640,5324660,8143141,3623650,5632255,3569360,3277856,3998808,9281302,7254848,7075276,8616910,9367365,7766259,3396048,8338360,6945130,9928695,5066500,9450074,428591,176242,2361792,2884601,6514080,1942040,6609108,8628830,6068288,7031196,3505527,6410220,6908895,9897904,6345296,5878930,1115341,8229144,7770859,5489152,9850160,873581,4399318,2872835,5991300,1411122,5277968,4359562,728910,2193804,9517430,9488880,4525712,4520050,2909661,3532448,7140752,1341540,3542804,6897528,1012628,3340008,6015653,3128843,6413500,7327744,767516,5096389,9186784,202477,9465850,4439041,8434684,1360834,8948586,2946240,9468377,5675298,7882068,3046216,5583740,514022,4465697,5094180,8895729,6252532,8387000,1962630,1156736,2178354,9067057,3261389,8973805,8426407,7924328,897862,6719664,3933185,5536293,6066180,5515350,9099655,8247476,3176478,7099724,4713526,6676946,5120963,3128100,7649948,2773991,1906555,5412124,2178443,4021288,5048933,2751876,2579520,5010464,6263315,3774840,9083648,483185,4234662,3832597,1510960,8698032,3268250,3358052,3728944,8128512,957950,6741500,5834448,397874,4654128,6515380,3118690,689808,2558824,3709882,1445108,5312626,9252416,2019225,5046527,2543458,4363560,2851360,8968207,4409630,6130270,8318768,2864865,282415,4602016,9966692,251248,9742727,1353670,6188941,6247432,8175912,8513235,8265566,6402920,3307068,3641722,4587424,6154728,2278232,3915911,4560479,2850800,7888739,1961624,9500596,2344677,4943704,7817891,9501154,5557536,1927808,7468821,5323992,6882160,6746876,249881,9612075,2611904,4451116,5670427,1566362,9606040,3344968,4857312,578848,1839548,9245530,9436263,6006160,4221903,6797404,4656836,2278800,2691061,941744,1076018,8103141,8785734,8984550,6440090,4988740,4825784,6750274,7932950,3309480,6396100,7325300,4771280,5684049,2767774,1713000,7510270,4872784,6728678,5226056,4067017,1922240,6336122,8857102,1093472,5644126,6714336,3871474,2474491,4134445,6021904,613930,261250,6532455,8226608,6932532,3095252,6126376,706032,7515695,1931008,26448,8080667,1674292,778968,5750752,8878384,6004967,9550875,1071168,6186269,6050560,3678859,9372060,7332767,170784,4942950,5274848,3768338,2532067,9596016,2706103,8570360,1023248,4441784,8646925,3128575,7018028,9659584,5047810,8847328,8804984,9507080,7653988,5850982,2906690,3869560,656108,5902040,2396079,130488,8909120,5221768,5847594,1411500,620586,1351544,5624,2039625,3022272,6943904,9121008,5162491,8931232,5220936,9553244,4734001,3131392,9446240,2112680,4949125,6793152,5181220,7802527,1472460,8750443,3582078,6167640,9300875,1171384,7780728,1893485,9861990,1866392,1515929,7345880,7615886,8297367,3086789,3164543,1606348,9026290,8870850,4236428,3128952,526900,3024400,9033600,7223585,4708300,7509066,9230512,2451100,8848654,2247492,984386,8697666,4014897,8111796,9272830,7752576,2547428,7825888,4865736,93008,6868168,2862304,9908980,7332140,3434399,1677290,2727920,7258750,5824900,8221396,7070704,8421280,6968175,4370722,4923225,6415413,4547648,5822407,4216030,6803370,2910384,4147256,6697618,8310927,1983132,3837167,2388268,2846106,8646197,9235720,4009224,8659104,119500,4784971,6167971,2379935,9410296,1385556,131154,5342552,6962706,220160,5916333,9528500,3656672,7295312,3510300,8550084,8130980,9139479,2965186,1681008,4115280,4391532,1240524,3696438,9817314,9152555,8258377,8291756,267122,639200,8421711,8488290,4869280,1699752,6042052,9172192,2598385,6103310,2232362,9200628,2098816,6645422,2916764,2933679,4408768,2318552,8565000,9474962,110640,8581909,8335678,7444814,1437784,298256,70380,3423101,3582820,5865760,1122088,7060036,3686231,2822700,2545360,1542916,9159650,1544428,6004944,8043120,5680294,2236920,3853195,7207968,2012682,5921865,7802195,180155,1191252,5534060,2012660,8573924,670983,8723202,8948680,9645225,3144264,8493384,2082668,2318287,6481968,3976009,7998170,1113420,3853080,4503125,4040846,4542164,7185980,238320,1932163,6096580,1707266,6073417,9734807,580175,9377054,9177857,3848832,2215958,2579200,8811904,675042,2219394,6209812,1399896,7555566,769569,1749192,296960,9351709,472680,7089575,5057018,3254206,434839,1508254,8417653,5986228,2204224,3453641,8715520,5975250,4588512,6342021,4317210,4625690,5383486,2740642,2774975,6694300,1553313,8209132,375404,6485780,515392,5994842,1928647,3609316,7593250,5701385,6084640,9128280,4750984,9214620,9047100,3415,9214099,9825619,614079,1226166,442337,5047000,9270698,1019492,1630642,5990944,5512509,7741641,7511052,2320100,663700,3974865,4638675,1429575,9257120,7988593,9012006,2821675,1568252,2668242,9610243,8858097,9602630,3524908,7555136,6534000,9360357,9170705,1407560,2348480,4242400,1923716,4297425,6845994,6748796,4729550,7075300,5033005,3134206,6702236];
reader_token=[54,5400,8444,1714779,274,1875,8,600,16,6,571,10,76182,1962050,57792,232278,1441466,939497,5,4,678,1,4538484,7836784,2,988,72000,60,76,1,3,1,14203,9013,70128,30150,8,36,14,1,480,473030,4836080,4,702527,121744,875,231,419136,23695,12678,7844,11,7199632,309932,3732816,14210,60,20080,662736,50,14,3328,16064,5,51,7047840,1262142,28,60,9,236284,363621,48,4,61,1,81244,1905728,578991,15,17898,904,8,95396,3,624,790364,63,79780,6123623,364,67754,80,2,363,106,4,58,7991,1265600,2810,140356,30,7205435,996841,6,1398,1870464,246,6,12275,62060,802600,1576,8120,28078,29810,200518,8755,7418733,189986,1574288,1844832,1,68,6585,1562841,53236,748,2422,968540,812,1049508,7668170,9804,88,2,440432,450350,6697946,48,2965,45870,8,4,257741,6,9840,8240292,4039625,23,6006492,45760,1640,9,679924,363008,4,158133,15,7615,4,5,152,2200,6901487,997,9066786,609014,7880,414,40,737520,2,614,56330,1770,44,8,119632,89659,1,1,7,6840,871,112,126,5,300875,13,83547,3840,6750,38240,7096949,12320,325955,556402,149,6796,198,26,896,215680,9232920,868,600,7270159,1300,1,36448,1376,70,449463,88210,16,36,58,5379,965,63,30,1116,8,260,9168948,421025,4,112,795,73844,1622,9,10123,1,167418,60,1882816,3198550,6797,25,1034,168,882,84,30,9636560,10,6,1,1314775,467,312090,1,6666,5004,1,1394656,1760,187,168738,1,92009,50,5634143,6223,594396,168,759,73393,16,90,72,20,720,227,9082116,65310,34,696354,1562,50125,9091270,68,2375,596931,19,832910,703847,14324,4,36,2,188,18788,921880,6,658497,6,1920,7530652,862230,11344,975,64,139360,951,798,129797,6336,93276,255025,45340,33616,8,680,390142,16,481495,5,10184,5268,45584,950,4046956,218761,2232665,60,60,5554,24,6725,3280,92842,2,5776800,703672,9091592,200,672,7860,42987,698,300412,333025,824,958730,15160,8596364,2255,6616,952,3591,780,8809156,9788,49249,206,9256398,4,505430,748,8195,99805,5,325882,137644,5,75244,55,181,904,8,933052,2,3,78,1,1588996,3,9729291,1706,3784,4,1920375,94,385135,3659,20,3,3555,2176,5536,27,179,4,4420,8,75,1717080,158316,440,41,7536,424,152534,4921456,155942,855,118,2773632,36006,714,1,14,122,152,16,7235805,88,50,5800,1,368161,5336,9774187,36,14,6,58036,30268,1725078,176,30490,7920,2104,38230,23480,342,1814,72,5966,53720,527970,1886,83080,5,5514,70296,1866580,944,708,1,175,312,62700,418150,9,1759140,250,8,682150,2928,19,1881,6094,951668,7943665,7920,340560,638,4726,1,27125,43,2,970,153192,1825,38040,40,38,603770,542908,9140,37645,24,2,820,255,33856,7107102,5238852,1064,9776,1,32443,66126,42790,1278,2,1497994,495,762,98,236,149,3,1,944,4614864,44,12617,21,38929,151,906,17712,420848,5268957,5,1281,9120,8082,110,46528,2568060,247360,386,1,51,365982,600,155084,38182,2,86,52,402750,77440,710,520,4128,55,545,900,12651,964,1747,6,352,86,4475410,746698,28,9,1,1352,1517,8924535,83,2187533,1,49000,4540936,2,8,73275,150,16007,66,452,35424,17365,75,1500,80,9,915,110,7,333908,53380,476451,4,709508,9092,174752,2424004,60641,337,6800,762,92,1736,6885,362540,15500,8608,940,940564,3577960,98,13,509497,71,18,37,576,1236,18340,6370,35080,16842,9,8,7826375,17,166,577,867,1,386085,680,1878,250,120,4400,60,9549776,781,6681884,630,71209,12,888,90128,389084,91,9150075,400,5,7720740,860999,1138,3335,80,1963,1,36,183969,5,2,4536,41153,6812,8,8402,435210,12,9308,8168,733178,8841,6,7844655,86442,8928,512,1096565,1744,1309045,678,5,715980,1568,5536,211220,36,916400,48,5815314,2,178125,7,858012,7653,26574,42,2,49484,52168,1,1,80046,937,10,21568,901880,86064,1,2210560,155,433340,348667,1,97760,84,7941055,39032,19080,703280,4,7,1455009,155200,6048,35,324626,988,72485,74,1,100,656,2565277,221016,6368,8,286156,984955,45,610,3578142,28976,6,1,311632,67332,194642,54,1,2,778348,470696,168835,1,2,28,44,446006,25,617460,80,3595,7491,757,175,4120,81,4425,6954835,443976,101502,439349,5976,9643161,14,18,2702500,2,1363,4437660,6,5046368,13360,1,130156,683,463950,42,87055,7872443,8280,96333,1574920,79950,120262,942459,68,631096,1100,4155945,9859950,6033948,4432,960021,799647,41502,7100960,157664,65065,10,828,2782560,1,6719720,7783200,39428,1,58750,4060,564,1,2344204,5,2725146,99,5,180,946979,170,2,70918,1796,94990,309205,1472654,3236,53094,5,637255,2,2443,67325,1,20,1385,6,40595,3707946,5420380,1636157,191612,260740,8424,145,3425,1,10150,920,6,599885,8,34,60,1,1,5638,12000,59686,63239,9772,2629,9,514530,901280,47,10364,3055,87,1318,6644,98859,7049262,10154,12,2,4,123,72,766024,50450,6,5934720,5549745,40,4234722,123420,327444,728,24,973942,310556,408,48734,8283,13,1,51827,164,597111,10300,64,910000,8160,68,36686,397426,5338308,437172,5791,60162,124,860,292,937115,1503,5171584,533557,4,400,6954,4564334,1,50332,860,4467844,85,194,8400,7,1787874,5380,38,76146,63,2247224,4584,7976,172,164794,440,3194,7,13750,544600,5615308,2,184,6,78424,7490,484848,50,68164,593933,559066,235803,24,5154,58,170,59497,132272,83307,440,20752,6997,1341732,11,6300,280,17620,95156,170,12,1571588,285450,14170,459400,224,1957,55,31952,3104,9891458,3322586,2860440,19560,940,68,238960,18,56042,522660,42088,4795720];
reader_bit=[2,4,4,7,3,4,1,3,2,1,3,2,5,7,5,6,7,6,1,1,3,1,7,7,1,3,5,2,2,1,1,1,5,4,5,5,1,2,2,1,3,6,7,1,6,6,3,3,6,5,5,4,2,7,6,7,5,2,5,6,2,2,4,5,1,2,7,7,2,2,1,6,6,2,1,2,1,5,7,6,2,5,3,1,5,1,3,6,2,5,7,3,5,2,1,3,3,1,2,4,7,4,6,2,7,6,1,4,7,3,1,5,5,6,4,4,5,5,6,4,7,6,7,7,1,2,4,7,5,3,4,6,3,7,7,4,2,1,6,6,7,2,4,5,1,1,6,1,4,7,7,2,7,5,4,1,6,6,1,6,2,4,1,1,3,4,7,3,7,6,4,3,2,6,1,3,5,4,2,1,6,5,1,1,1,4,3,3,3,1,6,2,5,4,4,5,7,5,6,6,3,4,3,2,3,6,7,3,3,7,4,1,5,4,2,6,5,2,2,2,4,3,2,2,4,1,3,7,6,1,3,3,5,4,1,5,1,6,2,7,7,4,2,4,3,3,2,2,7,2,1,1,7,3,6,1,4,4,1,7,4,3,6,1,5,2,7,4,6,3,3,5,2,2,2,2,3,3,7,5,2,6,4,5,7,2,4,6,2,6,6,5,1,2,1,3,5,6,1,6,1,4,7,6,5,3,2,6,3,3,6,4,5,6,5,5,1,3,6,2,6,1,5,4,5,3,7,6,7,2,2,4,2,4,4,5,1,7,6,7,3,3,4,5,3,6,6,3,6,5,7,4,4,3,4,3,7,4,5,3,7,1,6,3,4,5,1,6,6,1,5,2,3,3,1,6,1,1,2,1,7,1,7,4,4,1,7,2,6,4,2,1,4,4,4,2,3,1,4,1,2,7,6,3,2,4,3,6,7,6,3,3,7,5,3,1,2,3,3,2,7,2,2,4,1,6,4,7,2,2,1,5,5,7,3,5,4,4,5,5,3,4,2,4,5,6,4,5,1,4,5,7,3,3,1,3,3,5,6,1,7,3,1,6,4,2,4,4,6,7,4,6,3,4,1,5,2,1,3,6,4,5,2,2,6,6,4,5,2,1,3,3,5,7,7,4,4,1,5,5,5,4,1,7,3,3,2,3,3,1,1,3,7,2,5,2,5,3,3,5,6,7,1,4,4,4,3,5,7,6,3,1,2,6,3,6,5,1,2,2,6,5,3,3,4,2,3,3,5,3,4,1,3,2,7,6,2,1,1,4,4,7,2,7,1,5,7,1,1,5,3,5,2,3,5,5,2,4,2,1,3,3,1,6,5,6,1,6,4,6,7,5,3,4,3,2,4,4,6,5,4,3,6,7,2,2,6,2,2,2,3,4,5,4,5,5,1,1,7,2,3,3,3,1,6,3,4,3,3,4,2,7,3,7,3,5,2,3,5,6,2,7,3,1,7,6,4,4,2,4,1,2,6,1,1,4,5,4,1,4,6,2,4,4,6,4,1,7,5,4,3,7,4,7,3,1,6,4,4,6,2,6,2,7,1,6,1,6,4,5,2,1,5,5,1,1,5,3,2,5,6,5,1,7,3,6,6,1,5,2,7,5,5,6,1,1,7,6,4,2,6,3,5,2,1,3,3,7,6,4,1,6,6,2,3,7,5,1,1,6,5,6,2,1,1,6,6,6,1,1,2,2,6,2,6,2,4,4,3,3,4,2,4,7,6,6,6,4,7,2,2,7,1,4,7,1,7,5,1,6,3,6,2,5,7,4,5,7,5,6,6,2,6,4,7,7,7,4,6,6,5,7,6,5,2,3,7,1,7,7,5,1,5,4,3,1,7,1,7,2,1,3,6,3,1,5,4,5,6,7,4,5,1,6,1,4,5,1,2,4,1,5,7,7,7,6,6,4,3,4,1,5,3,1,6,1,2,2,1,1,4,5,5,5,4,4,1,6,6,2,5,4,2,4,4,5,7,5,2,1,1,3,2,6,5,1,7,7,2,7,6,6,3,2,6,6,3,5,4,2,1,5,3,6,5,2,6,4,2,5,6,7,6,4,5,3,3,3,6,4,7,6,1,3,4,7,1,5,3,7,2,3,4,1,7,4,2,5,2,7,4,4,3,6,3,4,1,5,6,7,1,3,1,5,4,6,2,5,6,6,6,2,4,2,3,5,6,5,3,5,4,7,2,4,3,5,5,3,2,7,6,5,6,3,4,2,5,4,7,7,7,5,3,2,6,2,5,6,5,7];